1. Field of the Invention
This invention relates to the field of systems for converting object representations to images for graphical display, and in particular to a system for rendering a surface represented by a set of Bezier patches.
2. Description of the Related Art
There is a growing interest in the graphics, vision, and manufacturing communities to be able to acquire and digitally reproduce the shape and external appearance of objects for the purpose of transmission, display, and numerically controlled fabrication. This would have applications in product design, fast prototyping, reverse engineering, and digitizing shapes for the visual simulation, animation, and entertainment industries. Current advancement in laser range scanners now offers a promising methodology for fully-automated model acquisition of arbitrary objects. Several million points scanned on an arbitrary object can be converted easily into an irregular mesh of polygons. These polygons are then preferably converted into a parametric surface representation, which is a more compact and manipulable form. U.S. patent application Ser. No. 08/810,255 (atty. docket # 5201-05100) titled "System and method for parametric surface representation of objects using high order surface patches" filed Mar. 3, 1997, and authored by Nishit Kumar et al. provides a fully automated method for converting a polygonal representation into a set of Bezier patches. A method for rendering these patches is now desirable.
A Bezier patch is a two-dimensional Bezier curve. A Bezier curve is defined by the following equation: ##EQU1## where g.sub.i, 0.ltoreq.i.ltoreq.n, are control points as shown in FIG. 1A. The result is a curve that is formed by a weighted sum of the control points. In cubic form, equation (1) can be represented by the following matrix equation: ##EQU2## where G.sub.c is a column vector containing the Bezier curve control points. If G.sub.c is parameterized in order to vary as a function of a second coordinate t, this gives the two-dimensional surface: ##EQU3## Realizing that for 3rd order Bezier curves, G.sub.i (t) can be expressed in the matrix equation EQU G.sub.i (t)=T M G.sub.ci, (4)
an expanded form of equation (3) can be written ##EQU4##
Equation (5) is the matrix form of a bicubic Bezier patch. An example of such a patch is shown in FIG. 1B. Equation (5) is decomposable into three equations of the same form, one equation for each coordinate axis of the control points. For example, equation (5) could be written as EQU X(s,t)=S M G.sub.x M T.sup.T, (6) EQU Y(s,t)=S M G.sub.y M T.sup.T, (7)
and EQU Z(s,t)=S M G.sub.z M T.sup.T. (8)
A generalization of the Bezier patch referred to as a "rational Bezier patch" is often used. A rational Bezier patch has a fourth equation EQU W(s,t)=S M G.sub.w M T.sup.T, (9)
which is used in determining the equation of the points of the surface in the following way: the (x,y,z) points on the surface patch are given by ##EQU5## where 0.ltoreq.s,t.ltoreq.1.
Three properties of Bezier patches are noted here. A Bezier patch is completely contained within the convex hull formed by the control points which define the patch. One exemplary consequence of this is that it may be determined that a patch is not within the screen boundaries if none of the control points is within the screen boundaries. A desired affine transformation (e.g. rotation, translation, magnification) of a Bezier patch may be achieved by applying the transformation to the control points. An exemplary consequence of this is that the transformation may be applied before the patch is rendered, thereby providing a significant decrease in the associated computation. Finally, an affine transformation may be applied to the s,t parameters of a Bezier patch without inducing any variation in the patch. These three properties will be used in later discussion.
In addition to the surface coordinates of an object, Bezier patches may be used to represent other aspects of the object. Examples include patches which provide values for the normal to the surface (N), the direction of the light source (L), the direction of reflected objects (R), the surface color and opacity of an object (R,G,B,A), and the coordinates of a texture image to be mapped onto the surface (U,V). In addition to these primary attribute patches, secondary attribute patches may also be associated with an object for special effects. All of these attribute patches must be rendered during the rendering of the surface to provide realism and a variety of special effects.
The usage of Bezier patches advantageously provides a method for compact, high-quality representation of objects. This method also allows for efficient execution of affine transformations on the object. It is desirable to have a method for converting Bezier patches into sets of triangles or other polygons for which established graphics rendering, hardware exists.
SUMMARY Of THE INVENTION
The problems outlined above are in large part solved by a high order surface patch rendering system. A patch is rendered by subdividing a patch until the subpatches are sufficiently flat that they can be approximated by a quadrilateral, which can then be split diagonally and written to a rasterizer in the form of two triangles. In one embodiment, the patch rendering system receives rational coordinates (X,Y,Z,W) and attribute coordinates (color, opacity, texture) of control points of the Bezier surface patch. The patch rendering system divides and subdivides the surface patch by operating on the surface patch control points to produce subpatch control points. The rational coordinates of the control points are converted to spatial coordinates, and if the current subpatch is determined to be flat, the spatial coordinates and attributes of the subpatch corner points are provided to an output buffer in the form of triangle vertices with associated attributes.
The present invention contemplates a patch rendering system which includes a patch tessellation device for converting a Bezier surface patch having a set of control points to a plurality of triangles for display. The patch tessellation device comprises a patch buffer, a patch division unit, a homogeneous coordinate unit, and a corner unit. The patch buffer is configured to receive and store rational coordinates of current control points of a current surface patch. The patch division unit is coupled to receive the rational coordinates of the current control points from the patch buffer and configured to calculate rational coordinates of new control points for a new surface patch. The homogeneous coordinate unit is coupled to receive the rational coordinates of the new control points and configured to convert the rational coordinates of the new control points to spatial coordinates of the new control points. The corner unit is coupled to the homogeneous coordinate unit to receive the spatial coordinates of new control points which correspond to corner points of the new surface patch, and configured to provide the spatial coordinates for corner points of the new surface patch as triangle vertices to an output buffer if the new surface patch is classified as flat. In addition to the coordinates, the patch tessellation device may also operate on Bezier patches specifying attributes of the surface patches.